#include<vector>

using namespace std;

class Solution {
public:

    vector<vector<int>> dirs = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols));

        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col<cols; col++)
            {
                if(board[row][col]==word[0]){
                    bool flag = dfs(board, word, row, col, 0, visited);

                    if(flag){
                        return true;
                    }
                }
            }   
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int row, int col, int index, vector<vector<bool>>& visited){
        if(board[row][col]!=word[index]){
            return false;
        }

        if(index==word.size()-1){
            return true;
        }

        visited[row][col] = true;
        bool res = false;
        for(auto dir:dirs){
            int next_row = row+dir[0];
            int next_col = col+dir[1];
            if(next_row>=0 && next_row<board.size() && next_col>=0 && next_col<board[0].size() && !visited[next_row][next_col]){
                res = dfs(board, word, next_row, next_col, index+1, visited);
                if(res)break;
            }
        }

        visited[row][col] = false;
        return res;
    }
};